package week10;

import java.util.Deque;
import java.util.LinkedList;

/**
 *
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：31 ms, 在所有 Java 提交中击败了57.54% 的用户
 * 内存消耗：55.5 MB, 在所有 Java 提交中击败了29.54% 的用户
 * 通过测试用例：61 / 61
 * 炫耀一下:
 *
 */
public class Week10SlidingWindowMaximum {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;

        Deque<Integer> deque = new LinkedList<Integer>();
        for(int size = 0; size < k; size++) {
            for(;!deque.isEmpty() && nums[size] >= nums[deque.peekLast()];) {
                deque.pollLast();
            }
            deque.offerLast(size);
        }

        int[] windowArray = new int[length - k + 1];
        windowArray[0] = nums[deque.peekFirst()];
        for(int size = k; size < length; size++) {
            for(;!deque.isEmpty() && nums[size] >= nums[deque.peekLast()];) {
                deque.pollLast();
            }
            deque.offerLast(size);
            for(;deque.peekFirst() <= size - k;) {
                deque.pollFirst();
            }
            windowArray[size - k + 1] = nums[deque.peekFirst()];
        }

        return windowArray;

    }
}
